﻿/*
 * Copyright 20010-2011 Edward L. Stauff.                  Contact: <EdStauff@gmail.com>.
 * 
 * This file, "PrefixDictionary.cs", is part of the "Stauffware.Common" class library.
 * "Stauffware.Common" is free software: you can redistribute it and/or 
 * modify it under the terms of the GNU Lesser Public License as published by the 
 * Free Software Foundation, either version 3 of the License, or (at your option) 
 * any later version.
 * 
 * "Stauffware.Common" is distributed in the hope that it will be useful, 
 * but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser Public License for more 
 * details.
 * 
 * You should have received a copy of the GNU Lesser Public License along with 
 * the "Stauffware.Common.Time" sources.  If not, see <http://www.gnu.org/licenses/>.
 */

// If defined, we use a SortedList internally.  
// It not defined, we use an array that we keep sorted and grow ourselves as needed
// (which is currently broken).
#define USE_SortedList

using System;
using System.Collections.Generic;
using System.Text;

namespace Stauffware.Common.Core
{
	/// <summary>
	/// The result of searching a PrefixDictionary for a name or prefix.
	/// </summary>
	public enum PrefixMatch
	{
		/// <summary>
		/// No matches were found.
		/// </summary>
		None,

		/// <summary>
		/// More than one entry matched the given prefix.
		/// </summary>
		Ambiguous,

		/// <summary>
		/// One partial match was found.
		/// </summary>
		Partial,

		/// <summary>
		/// One complete match was found.
		/// </summary>
		Complete
	}

	//=========================================================================
	/// <summary>
	/// A dictionary that maps string keys to values, along with all unique 
	/// proper prefixes of the string keys.
	/// </summary>
	/// <typeparam name="T">the type of the value</typeparam>

	public class PrefixDictionary<T> 
	{
		private readonly bool IgnoreCase;

		private readonly SortedList<string, string> OriginalNames;	// key = lower case name (if ignoring case)
		private readonly SortedList<string, T> Entries;		// sorted by name
		private readonly IList<string> EntryKeys;	// wraps this.Entries.Keys

		/// <summary>
		/// Returns the value for the one-and-only match for the given name.
		/// Throws an exception on no matches or multiple matches.
		/// </summary>
		public T this[string name]
		{
			get
			{
				T value;
				PrefixMatch m = this.Lookup(name, out value);
				if (m == PrefixMatch.None)
					throw new Exception("no match found for \"" + name + "\"");
				if (m == PrefixMatch.Ambiguous)
					throw new Exception("multiple matches found for \"" + name + "\"");
				return value;
			}
		}

		/// <summary>
		/// Gets the number of items in the dictionary (the number of items explicitly
		/// added, not counting implicit abbreviations).
		/// </summary>
		public int Count { get { return this.Entries.Count; } }

		/// <summary>
		/// Gets a collection of strings containing all the names (just the full names,
		/// not the abbreviations), in order.
		/// </summary>
		public IEnumerable<string> Names 
		{ get { return this.OriginalNames != null ? this.OriginalNames.Values : this.Entries.Keys; } }

		/// <summary>
		/// Gets a collection of all the values, in order.
		/// </summary>
		public IEnumerable<T> Values { get { return this.Entries.Values; } }

		//-----------------------------------------------------------------------------

		/// <summary>
		/// Constructor.
		/// </summary>
		/// <param name="ignoreCase">whether to ignore the case of the names (keys)</param>
		public PrefixDictionary (bool ignoreCase) : this(16, 8, ignoreCase) { }

		/// <summary>
		/// Constructor.
		/// </summary>
		/// <param name="initialSize">the number of entries to allocate space for initially</param>
		/// <param name="ignoreCase">whether to ignore the case of the names (keys)</param>
		public PrefixDictionary (int initialSize, bool ignoreCase)
			: this(initialSize, 1 + (initialSize / 4), ignoreCase) { }

		/// <summary>
		/// Full-featured constructor.
		/// </summary>
		/// <param name="initialSize">the number of entries to allocate space for initially</param>
		/// <param name="growBy">the number of entries to grow by when more space is needed</param>
		/// <param name="ignoreCase">whether to ignore the case of the names (keys)</param>
		public PrefixDictionary (int initialSize, int growBy, bool ignoreCase)
		{
			Require.Condition(growBy > 0);

			this.Entries = new SortedList<string, T>(initialSize);

			// Entries.Keys is a live read-only wrapper for the internal list,
			// so we only need to grab it once
			this.EntryKeys = this.Entries.Keys;

			this.IgnoreCase = ignoreCase;

			if (ignoreCase)
				this.OriginalNames = new SortedList<string, string>(initialSize);
		}

		//-----------------------------------------------------------------------------
		/// <summary>
		/// Adds an item to the dictionary.  
		/// Returns true on success, false if the (complete) name has already been added.
		/// </summary>

		public bool TryAdd (string name, T value)
		{
			if (this.IgnoreCase)
			{
				string origName = name;
				name = name.ToLower();
				if (this.OriginalNames.ContainsKey(name))
					return false;
				this.OriginalNames.Add(name, origName);
			}

			T entry;
			if (this.Entries.TryGetValue(name, out entry) && !value.Equals(entry))
				return false;

			this.Entries.Add(name, value);
			return true;
		}

		//-----------------------------------------------------------------------------
		/// <summary>
		/// Adds an item to the dictionary.  Fails an assertion if the (complete) name
		/// has already been added.
		/// </summary>

		public void Add (string name, T value)
		{
			if (! this.TryAdd(name, value))
				throw new InputRequirement("\"" + name + "\" already in dictionary with a different value");
		}

		//-----------------------------------------------------------------------------
		/// <summary>
		/// Removes an item from the dictionary.
		/// </summary>
		/// <param name="name">the name to remove</param>
		/// <returns>true if it was removed; false if it wasn't found</returns>

		public bool Remove (string name)
		{
			if (this.IgnoreCase)
				name = name.ToLower();
			this.OriginalNames.Remove(name);
			return this.Entries.Remove(name);
		}

		//-----------------------------------------------------------------------------
		/// <summary>
		/// Removes all entries from the dictionary.
		/// </summary>

		public void Clear ( )
		{
			this.OriginalNames.Clear();
			this.Entries.Clear();
		}

		//-----------------------------------------------------------------------------
		/// <summary>
		/// Searches the dictionary for an entry that matches the given name or prefix.
		/// </summary>
		/// <param name="name">the name to search for (complete or a prefix)</param>
		/// <param name="value">
		///		If exactly one match is found, this output parameter receives the value 
		///		associated with the key.  Otherwise, it is set to null.
		/// </param>
		/// <returns>the kind of match found</returns>

		public PrefixMatch Lookup (string name, out T value)
		{
			if (this.IgnoreCase)
				name = name.ToLower();

			value = default(T);

			if (this.Entries.TryGetValue(name, out value))
				return PrefixMatch.Complete;

			int n = this.FindAPrefixMatch(name);

			if (n < 0)
				return PrefixMatch.None;

			// see if there are other partial matches
			if ((n > 0) && this.EntryKeys[n-1].StartsWith(name))
				return PrefixMatch.Ambiguous;
			if ((n < this.EntryKeys.Count - 1) && this.EntryKeys[n+1].StartsWith(name))
				return PrefixMatch.Ambiguous;

			value = this.Entries.Values[n];
			return PrefixMatch.Partial; 
		}

		//-----------------------------------------------------------------------------
		// Returns the index of an item for which the given name is a prefix.
		// There may be additional matching items immediately before or after.
		// Returns -1 if not found.

		private int FindAPrefixMatch (string name)
		{
			// binary search

			int low = 0;
			int high = this.Entries.Count - 1;

			while (low <= high)
			{
				int mid = low + ((high - low) / 2);

				int comp = String.Compare(name, 0, this.EntryKeys[mid], 0, name.Length);

				if (comp > 0)
					low = mid + 1;
				else if (comp < 0)
					high = mid - 1;
				else
					return mid; // key found
			}

			return -1;	// not found
		}

		//-----------------------------------------------------------------------------

	}
}
